#
# Created by Administrator on 2021/7/28 AT 15:42.
#
# 给你一个整数数组 nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。
#
# 如果数组中不存在满足题意的整数，则返回 0 。

# 输入：nums = [21,4,7]
# 输出：32
# 解释：
# 21 有 4 个因数：1, 3, 7, 21
# 4 有 3 个因数：1, 2, 4
# 7 有 2 个因数：1, 7
# 答案仅为 21 的所有因数的和。
from typing import List


class Solution:
    def sumFourDivisors(self, nums: List[int]) -> int:
        """
        找到数组中每个数的所有因数
        :param nums:
        :return:
        """
        ans = 0
        for x in nums:
            [ele_num, total] = self.helper(x)
            if ele_num == 4:
                ans += total
        return ans

    def helper(self, num: int):
        if num == 1:
            return [1, 1]
        i = 2
        element = set()
        while i * i <= num:
            if num % i == 0:
                element.add(i)
                element.add(num // i)
            i += 1
        return [len(element) + 2, sum(element) + num + 1]


class Solution2:  # 题解
    def sumFourDivisors(self, nums: List[int]) -> int:
        ans = 0
        for num in nums:
            # factor_cnt: 因数的个数
            # factor_sum: 因数的和
            factor_cnt = factor_sum = 0
            i = 1
            while i * i <= num:
                if num % i == 0:
                    factor_cnt += 1
                    factor_sum += i
                    if i * i != num:  # 判断 i 和 num/i 是否相等，若不相等才能将 num/i 看成新的因数
                        factor_cnt += 1
                        factor_sum += num // i
                i += 1
            if factor_cnt == 4:
                ans += factor_sum
        return ans


if __name__ == '__main__':
    sol = Solution()
    print(sol.sumFourDivisors(nums=[21, 4, 7]))
    print(sol.sumFourDivisors(nums=[1, 2, 3, 4, 5]))
